package main

import (
	"fmt"
)

/*
  旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

进阶：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？


示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
 */

// 方法一： 使用额外的数组来记录
func rotate1(nums []int, k int)  {
	l := len(nums)
	temp := make([]int, l)
	for i := 0; i < l; i ++ {
		temp[(i + k) % l] = nums[i]
	}
	copy(nums, temp)
	fmt.Println(nums)
}

// 方法二 翻转数组
func rotate2(nums []int, k int)  {
	reverse := func(num []int) {
		left, right := 0, len(num) - 1
		for left < right {
			num[left], num[right] = num[right], num[left]
			left ++
			right --
		}
	}
	l := len(nums)
	reverse(nums)
	reverse(nums[:(k % l)])
	reverse(nums[(k % l):])
	fmt.Println(nums)
}

func main() {
	rotate1([]int{1,2,3,4,5,6,7}, 3)
	rotate2([]int{-1,-100,3,99}, 2)
}
